/*
  描述
  输入一棵节点数为 n 二叉树，判断该二叉树是否是平衡二叉树。
  在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树
  平衡二叉树（Balanced Binary Tree），具有以下性质：
  它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，
  并且左右两个子树都是一棵平衡二叉树。
*/
// 思考，可否通过遍历解决，如果可以，每个节点需要做什么
function IsBalanced_Solution (pRoot) {
  // 计算深度的函数
  const depth = (root) => {
    if (!root) return 0
    const left = depth(root.left)
    const right = depth(root.right)
    return Math.max(left, right) + 1
  }
  if (!pRoot) return true
  const gap = Math.abs(depth(pRoot.left) - depth(pRoot.right))
  if (gap <= 1) return IsBalanced_Solution(pRoot.left) && IsBalanced_Solution(pRoot.right)
  else return false
}